{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recurrent Neural Network: Introduction\n",
    "\n",
    "To motivate the RNN architecture let's consider an example.\n",
    "\n",
    "We want to perform sentiment analysis on a movie review dataset. There are two types of reviews in the dataset: positive and negative. We want to build a classifier to perform binary classification on this dataset. \n",
    "\n",
    "So far we have studied two types of **feedforward MLP** classifiers:\n",
    "- Fully-connected (FC) Neural Network \n",
    "- Convolutional Neural Network (CNN)\n",
    "\n",
    "These two classifier models require the entire input data at each step of the training. Usually the input data is a sequence of numbers that are arranged:\n",
    "- As a 2D or 3D matrix (e.g., image) or\n",
    "- As 1D vector (e.g., sequence of words in a sentence). \n",
    "\n",
    "Irrespective of the type of the data, we have to feed the entire sequence as a single data point to the above classifiers. Let's solve the above sentiment classification problem using a FC network or CNN.\n",
    "\n",
    "- But what would be the input to the classifier?\n",
    "\n",
    "Unlike the image classification problem, input in text classification is \n",
    "- Not numeric \n",
    "- Not of fixed length\n",
    "\n",
    "Let's illustrate the nature of the text input using a simple example. Say that we have only 6 reviews in our dataset along with the respective sentiment tags:\n",
    "\n",
    "1. Fellini created magic in Eight-and-Half! (POSITIVE)\n",
    "2. Disgusting! (NEGATIVE)\n",
    "3. The longest bore on celluloid! (NEGATIVE)\n",
    "4. I can watch Roma forever! (POSITIVE)\n",
    "5. Worst than the previous one! (NEGATIVE)\n",
    "6. Coppola's masterpiece! (POSITIVE)\n",
    "\n",
    "Observe that some samples (i.e., review) contain just one or two words. The largest review contains 5 words.\n",
    "\n",
    "To feed this dataset to a classifier, we need to perform preprocessing of the samples that include:\n",
    "- Map each word/phrase to a number\n",
    "- Transform each review into a fixed-length sequence of numbers (fixed-size vector)\n",
    "\n",
    "Mapping text tokens into numbers is known as **embedding**. There are various ways of creating text embedding. Let's not worry about this for now. Assume that for each token in the reviews, we have mapped them to a scalar number, such as:\n",
    "\n",
    "- Coppola: [9.1]\n",
    "- Fellini: [8.4]\n",
    "- etc.\n",
    "\n",
    "Usually the token embeddings are represented by a vector of numbers. For the sake of simplicity, we use a scalar number as embedding for each token. Using the embedding for each token, let's transform the reviews into numeric vectors.\n",
    "\n",
    "- Review 1:\n",
    "\n",
    "|  Fellini | created   | magic    | in   | Eight-and-half |  \n",
    "| :---:|:---:|:---:| :---:|  :---:| \n",
    "| [8.4   | 6.1  | 5 | 9 | 2 ]| \n",
    "\n",
    "- Review 2:\n",
    "\n",
    "| Disgusting  |\n",
    "| :---:|\n",
    "| [4.3 ]  |\n",
    "\n",
    "Observe that after transformation, we have **variable-length vectors**, i. e., each review vector has different length. We cannot feed these vectors directly to the MLP classifier. To create fixed-length vectors, we may add padding of zero values to each review vector. Let's use the maximum length of a review in this dataset (i.e., length 5 in review 1) to determine the fixed length of an input vector. Then, add padding as necessary to ensure that each review vector has length 5. For example, now the second review is transformed as follows.\n",
    "\n",
    "\n",
    "- Review 2 (with padding):\n",
    "\n",
    "| Disgusting  | (padding)  | (padding)   | (padding) | (padding) |  \n",
    "| :---:|:---:|:---:| :---:| :---:| \n",
    "| [4.3   | 0  | 0 | 0| 0 ]| \n",
    "\n",
    "\n",
    "Now that all 6 samples are fixed length 1D vector of numbers, we can use them to train the FC model or the CNN model, as shown below.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_FC_CNN.png\" width=900, height=700>\n",
    "\n",
    "Both of the above classifier models fall under the category of **feedforward neural network (FNN)**.\n",
    "\n",
    "## Feedforward Neural Networks are not Effective for Text Data\n",
    "\n",
    "Unfortunately, FNNs are not useful for most text classification problems. There are a couple of reasons.\n",
    "\n",
    "- Variable length input \n",
    "\n",
    "In some domains such as text processing, the length of the input data varies. But the FNNs need fixed-sized vectors as input. Padding the input data with zeros is rather inefficient. \n",
    "\n",
    "- Variable length output \n",
    "\n",
    "For some applications, the output may not be a fixed-size vector. For example, in language translation the length of the output sentence may vary from the input sentence. FNNs can only produce a fixed-size output.\n",
    "\n",
    "- Data has an inherent sequential structure\n",
    "\n",
    "Some type of data has a sequential/temporal structure. A good example is text data. Each word/phrase in a sentence is related to next word. So far, we assumed that our data points are independently and identically distributed. We created the models (e.g., FNNs) based on this assumption. However, this is not true for text data (it also applies to speech and video data). For example, it we permute the words in a review, it will be difficult to understand the semantic meaning of the complete review.\n",
    "\n",
    "The FNNs are not designed to handle sequential data well. Think about why CNNs are so powerful on image data. They are effective due to their ability to manipulate spatial structure of the image data. In a similar vein, if we want to design a powerful neural network model for text classification, we have to somehow be able to manipulate the temporal or sequential structure of the data.\n",
    "\n",
    "- Constant amount of computation\n",
    "\n",
    "The FNN models have a fixed architecture, which is defined by the number of layers. As a consequence, these models can only perform a fixed amount of computational steps. The core reason that RNNs are more exciting, as we will see shortly, is that they allow us to operate over sequences of vectors: Sequences in the input, the output, or in the most general case both. \n",
    "\n",
    "\n",
    "## An Effective Neural Network Architecture to Process Sequence Data\n",
    "\n",
    "To capture the sequential relationship between the words in a text, we can break down the input text (e.g., a review) into a sequence of tokens (words/phrases). Then, use each token as a single input to train the model.\n",
    "\n",
    "\n",
    "Let's consider a simple architecture for the new model, as shown below. It consists of a single neuron in the hidden layer. Say that we want to build a language model that will enable us to predict the next word based on previous sequence of words.\n",
    "\n",
    "At timestep $t_1$ this neuron takes an input (which is an embedding of the current word \"Fellini\"). For each token, the next token is its label.\n",
    "\n",
    "The neuron at $t_1$ computes a value for the next word \"created\" in the output. This value carries information of the first word. It is fed back to the input of the next timestep $t_2$ which also takes the next word \"created\" for processing. At the second timestep $t_2$ we have two input values: one value from the previous timestep carrying information about the past word, and the current word.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_1.png\" width=700, height=500>\n",
    "\n",
    "The above network is trained for a single sample (e.g., a single review) by repeatedly or recurrently feeding each token over time. The output of each learning step is fed into the input of the next step. As a consequence, output at any timestep is computed based on the input from all previous timesteps. For example, the output at timestep $t_4$ is computed based on the signals from $t_1$ to $t_4$.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_1a.png\" width=700, height=500>\n",
    "\n",
    "## Text Processing is About Creating Memories\n",
    "\n",
    "Essentially what is happening in the above scenario is that the network is building some type of **memory** of the past words to infer the next word in the sequence. The middle layer in the figure (shown below) acts as a **memory state or hidden state** that stores past information. The past information is used together with the current input to determine the current output. \n",
    "\n",
    "This inference process is akin to our reading process. When we read a sentence, we don't read the entire text as a single unit. Instead we process the sentence token-by-token keeping memories of what we processed before. Biological intelligence processes information incrementally while **maintaining an internal model of what it’s processing**, built from past information and constantly updated as new information comes in.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_2.png\" width=700, height=500>\n",
    "\n",
    "\n",
    "## A New Architecture for Processing Sequence Data\n",
    "\n",
    "The above illustration can be used to design a new type of neural network for processing sequence data such as text. There are three different layers in this architecture: input layer, hidden state layer, and the output layer, as shown below. We assume that the hidden state layer consists of only one neuron.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_3.png\" width=700, height=500>\n",
    "\n",
    "The hidden state stores sequence information using a hidden state variable, denoted by $h$. The hidden state $h_t$ at timestep $t$ is computed by a FC layer based on the input $x_t$ at timestep $t$ and the hidden state information $h_{t-1}$ from previous timestep $t-1$: \n",
    "\n",
    "- $h_t = f(x_t, h_{t-1})$\n",
    "\n",
    "In simple cases the output is equal to the hidden state, i.e.,\n",
    "\n",
    "- $y_t = h_t$\n",
    "\n",
    "However, in more complex scenarios, the hidden state at $t$ is used to compute the output at $t$ by using another FC layer:\n",
    "\n",
    "- $y_t = g(h_t)$\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_OutputLayer.png\" width=600, height=400>\n",
    "\n",
    "\n",
    "In this new architecture, the same two FC layers (one for the hidden state and the other for the output) are **recurrently** used for each token of the sample. What is distinctive about this architecture is that its hidden state is fed into its input, creating a loop or cycle. This architecture is unlike previous neural networks, which don't have any loop. This cyclic architecture is known as **Recurrent Neural Network (RNN)**. \n",
    "\n",
    "In the above figure (right), the RNN architecture is shown. The left figure is the same network that is unrolled through time. The same recurrent computation is represented once per timestep. A RNN looks very much like a FNN network, except it also has connections pointing backward, as shown below.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_4.png\" width=500, height=400>\n",
    "\n",
    "## Recurrent Neural Network (RNN) \n",
    "\n",
    "\n",
    "Let's generalize the architecture of a RNN. In the above RNN illustration, our input was a scalar, thus we used a single neuron at the hidden layer, which produces a scalar hidden output. \n",
    "\n",
    "For processing vector inputs, we create a layer of recurrent neurons (below right). At each timestep $t$, every neuron receives both the input vector $\\vec{x}_t$ and the hidden state vector $\\vec{h}_{t-1}$ from the previous timestep. \n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_5.png\" width=800, height=600>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## RNN: Signal Propagation\n",
    "\n",
    "Let's present how a signal is propagated forward in RNNs for a single sample. We need to be careful about the meaning of timestep in the context of RNNs. In a typical optimization algorithm, such as in gradient descent, we often refer iteration $t$ as time $t$. However, time in RNNs refers to **steps within an iteration**. \n",
    "\n",
    "Usually, each recurrent neuron has two sets of weights: \n",
    "- Input weights $\\vec{w}_{xh}$: for the inputs $\\vec{x}_t$  \n",
    "- Recurrent weights $\\vec{w}_{hh}$: for the hidden state outputs of the previous timestep $\\vec{h}_{t-1}$ \n",
    "\n",
    "If we consider the whole recurrent layer instead of just one recurrent neuron, we can place all the weight vectors in two weight matrices, $\\pmb{W}_{xh}$ and $\\pmb{W}_{hh}$. \n",
    "\n",
    "Assuming the an input vector is $d$-dimensional and there are $k$ recurrent neurons, the size of the weight matrices are defined as follows.\n",
    "\n",
    "- $\\pmb{W}_{xh}$: size $d \\times k$ - containing the connection weights for the inputs of the current timestep.\n",
    "\n",
    "- $\\pmb{W}_{hh}$: size $k \\times k$ - containing the connection weights for the hidden outputs of the previous timestep.\n",
    "\n",
    "\n",
    "Now consider a single iteration in which a sequence of timesteps is denoted by  $t = 1,...,T$. Then, the hidden-state output for a single input at timestep $t$ is calculated as follows:\n",
    "\n",
    "$\\vec{h}_t = \\phi \\otimes (\\pmb{W}_{xh}^T\\vec{x}_t + \\pmb{W}_{hh}^T\\vec{h}_{t-1} + \\vec{b}_h)$\n",
    "\n",
    "Note that $\\vec{h}_t$ is a 1D vector of size $k$. Also, $\\vec{b}_h$ is the bias vector of size $k$ containing each neuron’s bias term. The $\\phi(·)$ is an activation function (e.g., tanh). Note that the activation function is applied element-wise. Since the hidden-state output is a vector, the activation needs to be applied to each component of the vector.\n",
    "\n",
    "\n",
    "We can compute a recurrent layer’s output in one shot for a whole mini-batch by placing all the inputs at timestep $t$ in an input matrix $\\pmb{X}_t$. Say that there are $m$ samples in the mini-batch, each sample containing $d$ features. We define the size of the input and hidden-state output matrices as follows.\n",
    "\n",
    "- $\\pmb{X}_t$: $m \\times d$ - containing the inputs for all instances.\n",
    "\n",
    "- $\\pmb{H}_t$: $m \\times k$ - containing the layer’s outputs at timestep $t$ for each instance in the mini-batch.\n",
    "\n",
    "Then, the hidden-state output for a mini-batch input at timestep $t$ is calculated as follows:\n",
    "\n",
    "\n",
    "$\\pmb{H}_t = \\phi \\otimes (\\pmb{X}_t\\pmb{W}_{xh} + \\pmb{H}_{t-1}\\pmb{W}_{hh} + \\vec{b}_h)$\n",
    "\n",
    "=> $\\pmb{H}_t = \\phi \\otimes ([\\pmb{X}_t  \\pmb{H}_{t-1}]\\pmb{W} + \\vec{b}_h)$\n",
    "\n",
    "where \n",
    "\n",
    "$ \\pmb{W} =\n",
    "\\begin{bmatrix}\n",
    "  \\pmb{W}_{xh}  \\\\\n",
    "  \\pmb{W}_{hh} \n",
    " \\end{bmatrix}\n",
    "$\n",
    "\n",
    "The weight matrices $\\pmb{W}_{xh}$ and $\\pmb{W}_{hh}$ are often concatenated vertically into a single weight matrix $\\pmb{W}$ of shape $(d + k) \\times k$.\n",
    "\n",
    "The notation $[\\pmb{X}_t  \\pmb{H}_{t-1}]$ represents the horizontal concatenation of the matrices $\\pmb{X}_t$ and $\\pmb{H}_{t-1}$.\n",
    "\n",
    "\n",
    "As mentioned earlier, in a simple RNN architecture, the output vector is equal to the hidden-state vector.\n",
    "\n",
    "$\\pmb{Y}_t = \\pmb{H}_t$\n",
    "\n",
    "Here, the size of the output vector is:\n",
    "\n",
    "- $\\pmb{Y}_t$: $m \\times k$ - containing the layer’s outputs at timestep $t$ for each instance in the mini-batch.\n",
    "\n",
    "In general, for complex RNN architectures, the output vector is computed as follows:\n",
    "\n",
    "$\\pmb{Y}_t = \\phi \\otimes (\\pmb{H}_t\\pmb{W}_{hy} + \\vec{b}_y)$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_6_Weights.png\" width=800, height=600>\n",
    "\n",
    "\n",
    "## RNN: Deep Neural Network (DNN)\n",
    "\n",
    "So far, we have seen that the RNN models contain only one hidden state layer. It is possible to stack multiple hidden state layers to create deep RNNs. We will discuss this type of deep RNN architecture later.\n",
    "\n",
    "A RNN with only one hidden state layer can be a DNN. It is deep not in space, but in time. For a long sequence, we have to extend the recurrent computation deep into time. \n",
    "\n",
    "In feedforward neural networks (FC or CNN), the depth of a network is defined in **space**, i.e., with respect to the number of hidden layers. More fundamentally, the network depth represents the length of the path that an input signal has to pass through to reach the final state in the computation. In FNNs, this length is defined by the depth of a network.\n",
    "\n",
    "But in RNNs, a signal propagates through time to reach the final state via recurrence. Thus, the amount of the recurrence is a measure of the depth of a RNN. In other words, in RNNs the network depth is defined in **time**. To process long input sequences we need to build deep RNNs.\n",
    "\n",
    "\n",
    "## RNN vs FNN: Model Complexity and Computational Complexity\n",
    "\n",
    "Since RNNs always use the same model parameters (two weight matrices) for different timesteps, the number of RNN model parameters does not grow as the number of timesteps increases. Thus, RNNs are memory efficient.\n",
    "\n",
    "However, the computational complexity of a RNN could explode primarily depending on the length of the input sequence. The computational complexity will increase with model complexity (e.g., multiple hidden state layers, both forward and backward processing, etc.).\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Various RNN Architectures: Various Types of Sequence Data\n",
    "\n",
    "\n",
    "\n",
    "So far, we have assumed that the length of the input sequence and output sequence are the same. In practice, this may not hold true. We encounter scenarios in which the length of input sequence varies from that of the output sequence. In such case, we will have to adapt the simple RNN architecture.\n",
    "\n",
    "Below we discuss three broad cases of input-output sequence-length variation, and give suitable RNN architectures, as shown below.\n",
    "- Many-to-Many: Sequence-to-Sequence\n",
    "- Many-to-One: Sequence-to-Vector\n",
    "- One-to-Many: Vector-to-Sequence\n",
    "\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_VariousTypes.png\" width=900, height=700>\n",
    "\n",
    "## Many-to-Many: Sequence-to-Sequence\n",
    "\n",
    "Consider the problem of parts of speech (POS) tagging. In this problem, we have to mark up a word in a text as corresponding to a particular part of speech, based on both its definition and its context. For example, given the sentence \"Life is beautiful\", we will have to infer the POS tag for each of the token in this sentence (left figure below). In this problem the length of the input sequence is equal to the length of the output sequence. Also both sequences are synced. Thus, it's a many-to-many mapping. We can use the simple RNN architecture that we presented previously for solving this type of problem.\n",
    "\n",
    "Other examples that use this type of sequence-to-sequence RNN models include:\n",
    "- Stock price prediction\n",
    "- Named entity recognition\n",
    "- Pose estimation\n",
    "- Video classification where we wish to label each frame of the video\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_ManyToMany.png\" width=900, height=700>\n",
    "\n",
    "\n",
    "Now consider **another type of many-to-many mapping** in which the input and output sequence length are not the same, and they are not synced. As an example, consider machine translation (right figure above). The input sentence in English has 3 tokens, but the output (inferred) sequence (sentence in French) has 4 tokens.\n",
    "\n",
    "The above sequence-to-sequence problem is solved by designing two networks.\n",
    "- Sequence-to-vector (encoder)\n",
    "- vector-to-sequence (decoder)\n",
    "\n",
    "The encoder converts the English sentence into a single vector representation. Then, the decoder takes this vector as input and decodes it into a sentence in French. \n",
    "\n",
    "\n",
    "\n",
    " \n",
    "\n",
    "## Many-to-One: Sequence-to-Vector\n",
    "\n",
    "In some problems, input is a sequence, but output is a vector. For example, consider the movie sentiment analysis problem. The output could be binary (positive sentiment or negative sentiment), or a moving ranking between 1 to 5. In either case, we feed the network the entire sequence of the review. At each timestep, the network produces an output. We don't need outputs from all timesteps except the last one where the network makes an inference about the review. This scenario can be modeled by a sequence-to-vector network, as shown below.\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_ManyToOne.png\" width=500, height=300>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## One-to-Many: Vector-to-Sequence\n",
    "\n",
    "Consider an example of image captioning. The input could be an image (or the output of a CNN), which is a vector, and the output could be a caption for that image (i.e., a sequence of words). \n",
    "\n",
    "Another example could be music generation. As input we may provide the genre or even nothing (i.e., a null vector), but the output is a sequence of notes representing a piece of music.\n",
    "\n",
    "This type of problems can be modeled by using a vector-to-sequence RNN architecture, as shown below.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_OneToMany.png\" width=500, height=300>\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
